Valid palindrome

Time: O(N); Space: O(1); easy

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note:

  • For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: “A man, a plan, a canal: Panama”

Output: True

Explanation:

  • “amanaplanacanalpanama”

Example 2:

Input: “race a car”

Output: False

Explanation:

  • “raceacar”

[1]:

class Solution1(object):
    def isPalindrome(self, s):
        """
        :type s: string
        :rtype: boolean
        """
        i, j = 0, len(s) - 1
        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1
            if s[i].lower() != s[j].lower():
                return False
            i, j = i + 1, j - 1
        return True

[2]:

sol = Solution1()
s = "A man, a plan, a canal: Panama"
assert sol.isPalindrome(s) == True
s = "race a car"
assert sol.isPalindrome(s) == False
s = ""
assert sol.isPalindrome(s) == True